// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* Primeira DFS: Armazena a ordem recursiva dos vertices */
void kosarajuDfs1(vector<int> graph[], int n, int curr, bool blocked[], int matriz[]) {
  /* Vertice visitado */
  blocked[curr] = true;

  vector<int>::iterator it;

  /* Chama recursividade para vertices nao visitados tal que curr->*it */
  for (it = graph[curr].begin();it != graph[curr].end();++it)
    if (!blocked[*it])
      kosarajuDfs1(graph, n, *it, blocked, matriz);

  /* Armazena ordem da recursividade */
  matriz[matriz[0]++] = curr;

  return;
}

/* Segunda DFS: Utilizando grafo reverso e a matriz de ordem recursiva(DFS1) gera entao a matriz id(componentes fortemente conectados) */
void kosarajuDfs2(vector<int> graph[], int n, int curr, bool blocked[], int id[]) {
  /* Vertice visitado */
  blocked[curr] = true;
  /* Armazena id */
  id[curr+1] = id[0];

  vector<int>::iterator it;

  /* Processa para todos os vertices nao visitados tal que curr->*it */
  for (it = graph[curr].begin();it != graph[curr].end();++it)
    if (!blocked[*it])
      kosarajuDfs2(graph, n, *it, blocked, id);

  return;
}

/* Algoritmo kosaraju */
/* id[] -> Matriz com indices de componentes fortemente conectados (DFS2) */
void kosaraju(vector<int> graph1[], int n, int id[]) {
  bool blocked[MAX];              // Vertices visitados
  int matriz[MAX];                // Matriz que armazena ordem da DFS1 (DFS1)
  vector<int>::iterator it;
  vector<int> graph2[MAX];        // Grafo reverso

  /* Inverte o grafo de entrada */
  for (int i = 0;i < n;i++)
    for (it = graph1[i].begin();it < graph1[i].end();++it)
      graph2[*it].push_back(i);

  /* Seta vertices nao visitados */
  for (int i = 0;i < n;i++) blocked[i] = false;

  matriz[0] = 1;

  /* Roda DFS1 para todos os vertices */
  for (int i = 0;i < n;i++)
    if (!blocked[i])
      kosarajuDfs1(graph1, n, i, blocked, matriz);

  /* Seta vertices nao visitados */
  for (int i = 0;i < n;i++) blocked[i] = false;

  id[0] = 0;

  /* Roda DFS2 para todos os vertices utilizando a ordem do DFS1 */
  for (int i = n;i > 0;i--)
    if (!blocked[matriz[i]]) {
      kosarajuDfs2(graph2, n, matriz[i], blocked, id);
      id[0]++;   // Muda indice do componente
    }

  return;
}
